1. Field of the Invention
Methods and apparatuses consistent with the present invention relate to tag generation in a broadcast encryption (BE) system. More particularly, the present invention relates to a tag generation method in a BE system for efficiently reducing a tag size.
2. Description of the Related Art
The broadcast encryption (BE) system enables a transmitter, that is, a broadcast center, to effectively transmit information only to intended users among all users. The BE should be available effectively whenever a set of the intended users arbitrarily and dynamically changes. An important property of the BE is to revoke or exclude an unintended device or user, for example, an illegal user or an expired user.
In order to revoke or exclude an unintended device or user, each device stores a different key set assigned to that particular device, and a service provider stores the whole key set of the all devices.
Various schemes have been suggested for such a BE system. Generally, the BE system employs a layered node structure. Alternatively, the BE system may be implemented using a hierarchical hash-chain broadcast encryption scheme (HBES).
FIG. 1 depicts how to assign keys to nodes, respectively, in a conventional BE system. Referring to FIG. 1, nodes 0 through 3 are arranged in a circle. The respective nodes 0 through 3 correspond to users in the BE system. Each node i is assigned a unique node key Ki. In other words, the node key K0 is assigned to the node 0, the node key K1 is assigned to the node 1, the node key K2 is assigned to the node 2, and the node key K3 is assigned to the node 3.
To enable private communications between or among authorized users, a certain key shared only by the authorized users should be assigned to the nodes of the circular structure. For doing this, the unique keys assigned to the nodes are consecutively applied to a one-way hash function to generate key values, that is, key sets. The generated key values are assigned to the nodes, respectively, in a manner as shown in Table 1.
TABLE 1Node 0Node 1Node 2Node 3Key setK0H (K0)HH (K0)HHH (K0)HHH (K1)K1H (K1)HH (K1)HH (K2)HHH (K2)K2H (K2)H (K3)HH (K3)HHH (K3)K3
In Table 1, ‘H’ denotes the one-way hash function, and HH(K0)=H(H(K0)). The one-way hash function takes an input value of an arbitrary length and produces an output value of a fixed length. The one-way hash function has properties such that it is infeasible to find the input value using a given output value, and it is impossible to find another input value that produces the same output value as a given input value. In addition, it is impossible to find two different arbitrary input values that produce the same output value.
As mentioned above, the hash function is a function that is advantageously applied for data integrity, authentication, repudiation prevention, and the like. The one-way hash function may be HBES SHA −1.
Referring back to FIG. 1, in case that only the nodes 0, 1 and 2 want to secure a safe, or private, communication channel, they use HH(K0) as an encryption key. In doing so, the nodes 0, 1 and 2 may store HH(K0) corresponding to the encryption key or easily compute HH(K0) using a stored value. However, the node 3 cannot compute HH(K0) corresponding to the encryption key, using its stored HHH(K0).
Thus, a node excluded from the encryption communication channel, such as the node 3 in the above example, is referred to as a revoked node, and a nodes constructing the private communication channel are referred to as a privileged nodes. Therefore, in the above example, nodes 0, 1 and 2 would be the privileged nodes. The set of the nodes arranged in a circle are referred to as a node group.
To handle a large number of nodes, it is necessary to layer the structure of FIG. 1.
FIG. 2 depicts a layered structure of the circular node groups of FIG. 1.
As shown in FIG. 2, two layers of a layer 0 and a layer 1 are shown, and a node group at each layer consists of 4 nodes. The respective nodes are assigned the key values or key sets generated using the hash function in a manner as shown in Table 1. The nodes at the lowest layer 1 are leaf nodes.
Note that the nodes at the lower layer hold keys assigned to their parent nodes in the upper layer in the layered structure of FIG. 2. In addition, when a node is revoked from the communication channel, the parent node of the revoked node is also regarded as the revoked node.
For example, the node 3 of the node group 1 stores its assigned key set and the key set of the node 0 in the node group 0. If the node 1 of the node group 3 is revoked, the node 2 of the node group 0 is also regarded as the revoked node.
In the example, the nodes 3, 0 and 1 of the node group 0 can secure the encryption communication channel by using HH(K03), which is generated from the encryption key of the node 3 of the node group 0 K03 (0 denotes the number of the node group and 3 denotes the serial number of the node), as the encryption key.
The privileged nodes in the node group 3 can also secure the encryption communication channel by using HH(K32) generated from K32 as the encryption key.
Accordingly, a server is able to transmit the encrypted information to all the nodes but the node 1 of the node group 3 using HH(K03) and HH(K32) as the encryption key.
That is, the server transmits to the leaf nodes a temporary key encrypted using the selected encryption key as aforementioned, and content encrypted with the temporary key.
Upon receiving the encrypted data packets from the server, the leaf nodes require information as to which one of its stored keys is used to generate the encryption key and to decrypt the data packet.
Hence, when transmitting the encryption key, the server appends a tag to the data packets so that the leaf nodes can acquire the information relating to the encryption key. The tag contains information relating to the revoked nodes.
Thus, the leaf nodes can learn the encryption key of the received data packets and thus generate the encryption key by means of the information relating to the revoked nodes.
As the above examples illustrate, a transmission overhead, a storage overhead, and a computation overhead are necessary in the BE. The transmission overhead is a quantity of the header transmitted from the transmitter, the storage overhead is a quantity of a secret key stored by the user, and the computation overhead is a quantity of computation required for the user to acquire a session key. It is therefore desirable to reduce the overhead in the BE system, and specifically to reduce the transmission overhead according to the tag transmission.